package mianshi;

import niuke.ListNode;
import niuke.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * description:
 * author:张腾
 * date:2021-07-21
 */

/**
 * 给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
 */
public class _04_03 {
    public ListNode[] listOfDepth(TreeNode tree) {
        if (tree==null) return new ListNode[0];
        ArrayDeque<TreeNode> depth = new ArrayDeque<>();
        ArrayList<ListNode> res = new ArrayList<>();
        depth.addLast(tree);

        while (!depth.isEmpty()){
            ListNode dum = new ListNode();
            ListNode pre = dum;
            for (int size = depth.size(); size > 0; size--) {
                TreeNode node = depth.removeFirst();
                ListNode n = new ListNode(node.val);
                pre.next = n;
                pre = n;
                if (node.left!=null) depth.addLast(node.left);
                if (node.right!=null) depth.addLast(node.right);
            }
            res.add(dum.next);
        }
        ListNode[] ans = new ListNode[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }
}
